package com.clstu.leetcode;

/**
 * leetcode 52N皇后问题
 */
public class QueueN {
    public int totalNQueens(int n){
        //生成一个末尾n位为1的数
        int limit = 1<<n-1;
        //直接根据为信息返回结果
        return set(limit,0,0,0);
    }

    //编写方法根据位限制深度优先遍历得到n皇后的
    public int set(int limit,int colimit,int rightLimi,int leftLimi){
        //如果全部位都摆放完,找到1种解法
        if(limit == colimit){
            return 1;
        }
        int res = 0;
        //得到可以摆放皇后的所有位,1可以摆放
        int pos = limit & ~(colimit | rightLimi | leftLimi);
        //遍历回溯得到结果
        while(pos != 0){
            //得到最后的1也是本次放皇后的位置
            int lastOne = pos & (~pos+1);
            pos = pos-lastOne;//放一个皇后就去掉一个位置
            res =res+set(limit,colimit|lastOne,(rightLimi|lastOne)>>1,(leftLimi|lastOne)<<1);
        }
        return res;
    }
}
